package src.leetcode.everyday.hard_1547;

import java.util.Arrays;

public class minCost {
    public static void main(String[] args) {
        int mincost = new Solution().minCost(5, new int[]{1,3,4});
        System.out.println(mincost);
    }
}

class Solution {
    public int minCost(int n, int[] cuts) {
        int m = cuts.length;
        Arrays.sort(cuts);

        return cutmid(cuts, 0, m, 0, n);
    }

    private int cutmid(int[] cuts, int left, int right, int idx, int n) {
        if (left == right) return 0;
        if (left + 1 == right) return n - idx;

        int mid = idx + (n - idx) / 2;
        int ans = left;
        int min = Math.abs(cuts[ans] - mid);
        for (int i = left + 1; i < right; i++) {
            if(Math.abs(cuts[i] - mid) < min) {
                min = Math.abs(cuts[i] - mid);
                ans = i;
            }
        }

        return cutmid(cuts, left, ans, idx, cuts[ans]) + cutmid(cuts, ans + 1, right, cuts[ans], n) + n - idx;
    }
}
